栈和队列——用一个栈实现另一个栈的排序

Posted on | In ,

题目：一个栈中的元素为整型，现将栈中元素按从栈顶到栈底从大到小排序，值允许申请一个栈，不能再 申请额外的数据结构。

实现：
1.定义要排序的栈stack，辅助栈temp。
2.只要stack不为空，弹出栈顶数据int data = stack.pop(),一直进行如下操作：
1）若从stack.pop()比temp.peek()小或相等，则直接压入；
2）若从stack.pop()比temp.peek()大，则将弹出temp栈顶数据压入stack；直到temp的栈顶数据大于data，将data压入temp。
3.继续判断后面的数据，直到所有数据已经压入temp，最后将temp全部弹出，放入stack。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;
import java.util.Stack;
public class SortStackByStack {
	public static void sortStackByStack(Stack<Integer> stack) {
		Stack<Integer> temp = new Stack<>();
		//将stack中的所有数据弹出排序，压入到temp：从顶到底是从小到大的顺序
		while(!stack.isEmpty()) {
			int data = stack.pop();
			//这个小于符号反向的话，就可以对stack从栈顶到栈底小到大排序
			//一直循环比较stack.pop()和temp.peek()元素
			while(!temp.isEmpty() && temp.peek() < data) {
				stack.push(temp.pop());
			} //一直执行temp弹出并压入stack操作，直到temp.peek() > data则直接压入
			temp.push(data); 
		}
		//将temp中数据全部弹出压入stack
		while (!temp.isEmpty()) {
			stack.push(temp.pop());
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	//Test
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<>();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++){
			stack.add(sc.nextInt());
		}
		/*
		stack.add(1);
		stack.add(5);
		stack.add(2);
		stack.add(4);
		stack.add(0);*/
		sortStackByStack(stack);
		while (!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}
}